package 刷题.leedcode142;

import java.util.HashSet;
import java.util.Set;

//哈希表
public class Solution2 {
    public ListNode detectCycle(ListNode head) {
        //遍历链表每个结点并记录下来，若再次遇到，返回即可
        /*
        ListNode prev = head;
        Set<ListNode> seen = new HashSet<ListNode>();
        while(prev != null){
            if(seen.contains(prev)){
                return prev;
            }else{
                seen.add(prev);
            }
            prev = prev.next;
        }
        return null;

         */
        Set<ListNode> seen = new HashSet<>();
        ListNode prev = head;
        while(prev != null){
            if(!seen.add(prev)){
                return prev;
            }
            prev = prev.next;
        }
        return null;
    }
}
